package sort;

import java.util.Arrays;

public class MergeSort implements MySort {
    public static void main(String[] args) {
        int a[] = {8,9,1,7,2,3,5,4,6,0};
        //int a[] = {5,4};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(a);
        System.out.println(Arrays.toString(a));
    }

    @Override
    public void sort(int[] a) {
        int left=0;
        int right=a.length-1;
        int[] temp = new int[a.length];
        mergeSort(a,left,right,temp);
    }

    private void mergeSort(int[] a, int left, int right, int[] temp) {
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(a,left,mid,temp);
        mergeSort(a,mid+1,right,temp);
        merge(a,left,mid,right,temp);
    }

    private void merge(int[] array , int left, int mid, int right, int[] temp){
        int i=left;
        int j=mid+1;
        int index = 0;
        while(i<=mid&&j<=right){
            if(array[i]<array[j]){
                temp[index++] = array[i++];
            }else {
                temp[index++] = array[j++];
            }
        }

        while(i<=mid){
            temp[index++] = array[i++];
        }

        while(j<=right){
            temp[index++] = array[j++];
        }

        //复制到原数组
        for(int ii=left,jj=0;ii<=right;ii++,jj++){
            array[ii] = temp[jj];
        }
    }
}
